package com.hdu.other.tanxin;

import java.util.HashMap;
import java.util.Map;

public class lc2384 {
    class Solution {
        public String largestPalindromic(String num) {
           Map<Character, Integer> char2freq = new HashMap<>();
           for (char c : num.toCharArray()) {
               char2freq.put(c, char2freq.getOrDefault(c, 0) + 1);
           }
           StringBuilder left = new StringBuilder();
           char mid = 0;
           for (char curC = '9'; curC >= '0'; curC--)
           {
               Integer freq = char2freq.get(curC);
               if (freq != null && freq != 0) {
                   if (freq % 2 == 1 && mid == 0)
                   {
                       mid = curC;
                   }
                   if (left.length() > 0 || curC != '0')
                   {
                       for (int i = 0; i < freq / 2; i++)
                       {
                           left.append(curC);
                       }
                   }
               }
           }
           if (left.length() == 0) {
               if (mid == 0) {
                   return "0";
               } else {
                   return String.valueOf(mid);
               }
           }

           StringBuilder ans = new StringBuilder();
           ans.append(left);
           if (mid != 0) {
               ans.append(mid);
           }
           for (int i = left.length() - 1; i >= 0; i--)
           {
               ans.append(left.charAt(i));
           }

           return ans.toString();
        }
    }
}
